Logaritm discret

În matematică, pentru numerele reale date $a$ și $b$ , logaritmul $log b a$ este un număr $x$ astfel încât $b x = a$ . Analog, în orice grup G, se poate defini pentru orice număr întreg $k$ puterea b^k, iar logaritmul discret log_b a este un număr întreg k astfel încât b^k = a. În teoria numerelor, termenul cel mai frecvent utilizat este cel de indice: putem scrie x = ind_r a (mod m) (se citește „indicele lui $a$ în baza r modulo m”) pentru r^x ≡ a (mod m ) dacă r este o rădăcină primitivă a lui m și cmmdc (a, m) = 1.

Logaritmii discreți sunt rapid calculabili în câteva cazuri speciale. Totuși, nu se cunoaște nicio metodă eficientă pentru a-i calcula în general. Câțiva algoritmi importanți din criptografia cu cheie publică își bazează securitatea pe presupunerea că problema logaritmului discret în cadrul unor grupuri alese cu atenție nu are o soluție eficientă.

Definiție

Fie $G$ orice grup. Notăm operația de grup a acestuia cu semnele de înmulțire și elementul său neutru cu 1. Fie $b$ orice element al lui $G$ . Pentru orice număr întreg pozitiv $k$ , expresia $b k$ reprezintă produsul lui $b$ cu el însuși de $k$ ori:

b^{k}=\underbrace {b\cdot b\cdots b} _{k\;{\text{factori}}}.

În mod similar, fie $b - k$ produsul lui $b -1$ cu sine însuși de $k$ ori. Pentru $k =0$ , puterea $k$ este elementul neutru 0: $b 0 =1$ .

Fie $a$ un element al lui $G$ . Un întreg $k$ , care rezolvă ecuația $b k = a$ se numește logaritmul discret (sau pur și simplu logaritmul, în acest context) din $a$ în bază $b$ . Se scrie $k = log b a$ .

Exemple

Puterile lui 10

Puterile lui 10 formează o submulțime infinită G = {…, 0,001, 0,01, 0,1, 1, 10, 100, 1000, …} a numerelor raționale. Această mulțime G este un grup ciclic^⁠(d) în raport cu înmulțirea, iar 10 este generatorul. Pentru orice element $a$ al grupului, se poate calcula $log 10 a$ . De exemplu, log₁₀ 10000 = 4 și log₁₀ 0,001 = −3. Acestea sunt exemple ale problemei logaritmului discret.

Alți logaritmi în bază 10 din numerele reale nu sunt exemple ale problemei logaritmului discret, deoarece implică exponenți neîntregi. De exemplu, ecuația log₁₀ 53 = 1,724276... înseamnă că 10 ^1,724276... = 53. În timp ce exponenții întregi pot fi definiți în orice grup folosind produse și inverse, exponenții arbitrari din numerele reale necesită alte concepte, cum ar fi funcția exponențială.

Puterile unui număr real fix

Un exemplu similar este valabil pentru orice număr real diferit de zero $b$ . Puterile formează un subgrup multiplicativ G = {…, b ⁻³, b ⁻², b ⁻¹, 1, b ¹, b ², b ³, …} al numerelor reale nenule. Pentru orice element $a$ din G, se poate calcula $log b a$ .

Aritmetica modulară

Una dintre cele mai simple contexte pentru logaritmii discreți este grupul (Z_p)^×^⁠(d). Acesta este grupul înmulțirii modulo^⁠(d) $p$ , cu $p$ număr prim. Elementele sale sunt clase de congruență^⁠(d) modulo $p$ , iar produsul de grup a două elemente poate fi obținut prin înmulțirea obișnuită a elementelor întregi, urmată de reducerea modulo $p$ .

Puterea $k$ a unuia dintre numerele din acest grup poate fi calculată prin ridicarea la puterea $k$ și apoi găsirea restului împărțirii acestuia la $p$ . Când numerele implicate sunt mari, este mai eficient să se reducă modulo $p$ de mai multe ori pe parcursul calculului. Indiferent de algoritmul specific utilizat, această operație se numește exponențiere modulară^⁠(d). De exemplu, fie (Z₁₇)^× . Pentru a calcula 3⁴ în acest grup, se calculează 3⁴ = 81, apoi se împarte 81 la 17, obținând restul 13. Astfel 3⁴ = 13 în grupul (Z₁₇)^×.

Logaritmul discret este doar operația inversă. De exemplu, considerăm ecuația 3^k ≡ 13 (mod 17) pentru $k$ . Din exemplul de mai sus, o soluție este k = 4, dar nu este singura soluție. Deoarece 3¹⁶ ≡ 1 (mod 17) — după cum rezultă din mica teoremă a lui Fermat — rezultă, de asemenea, că dacă n este un număr întreg, atunci 3⁴⁺¹⁶ⁿ ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 × 1 ⁿ ≡ 13 (mod 17). Prin urmare, ecuația are un număr infinit de soluții de forma 4 + 16n. Mai mult, deoarece 16 este cel mai mic număr întreg pozitiv m care satisface relația 3^m ≡ 1 (mod 17), acestea sunt singurele soluții. În mod echivalent, mulțimea tuturor soluțiilor posibile poate fi exprimată prin constrângerea ca k ≡ 4 (mod 16).

Puterile elementului neutru

În cazul special în care $b$ este elementul neutru 1 al grupului G, logaritmul discret $log b a$ este nedefinit pentru $a$ diferit de 1, și orice număr întreg $k$ este un logaritm discret pentru $a = 1$ .

Proprietăți

Puterile se supun identității algebrice obișnuite $b k + l = b k b l$ . Cu alte cuvinte, funcția

f\colon \mathbf {Z} \to G

definită prin $f (k) = b k$ este un omomorfism de grup definit pe numerele întregi Z în raport cu operația de adunare, cu valori în subgrupul H al lui G generat^⁠(d) de $b$ . Pentru orice $a$ din H, există $log b a$ . În schimb, $log b a$ nu există pentru a care nu sunt din H.

Dacă H este infinit, atunci $log b a$ este, de asemenea, unic, iar logaritmul discret echivalează cu un izomorfism de grup^⁠(d)

\log _{b}\colon H\to \mathbf {Z} .

Pe de altă parte, dacă H este finit de ordinul n, atunci $log b a$ este unic numai până la congruența modulo n^⁠(d), iar logaritmul discret echivalează cu un izomorfism de grup

\log _{b}\colon H\to \mathbf {Z} _{n},

unde cu Z_n se notează grupul aditiv de numere întregi modulo n.

Formula familiară de schimbare a bazei pentru logaritmii obișnuiți rămâne valabilă: Dacă c este un alt generator al lui H, atunci

\log _{c}a=\log _{c}b\cdot \log _{b}a.

Algoritmi

Problemă nerezolvată în informatică:

Poate fi logaritmul discret calculat în timp polinomial pe un computer clasic?

(mai multe probleme nerezolvate din informatică)

Problema logaritmului discret este considerată netractabilă computațional. Adică, nu este cunoscut un algoritm clasic eficient pentru calculul logaritmilor discreți în general.

Un algoritm general pentru calculul $log b a$ în grupuri finite G este de a ridica b la puteri din ce în ce mai mari k până când se găsește a. Acest algoritm este uneori numit înmulțire de încercare. Este nevoie de timp de rulare liniar în raport cu dimensiunea grupului G și, prin urmare, exponențial în raport cu numărul de cifre din dimensiunea grupului. Prin urmare, este un algoritm în timp exponențial, care este practic doar pentru grupuri G mici.

Există algoritmi mai sofisticați, de obicei inspirați de algoritmi similari pentru factorizarea întregilor. Acești algoritmi rulează mai repede decât algoritmul naiv, unii dintre ei fiind proporționali cu rădăcina pătrată a mărimii grupului și astfel exponențial la jumătate din numărul de cifre din dimensiunea grupului. Totuși, niciuna dintre ele nu rulează în timp polinomial (în numărul de cifre din dimensiunea grupului).

Există un algoritm cuantic eficient datorat lui Peter Shor^⁠(d).^[1]

Algoritmi clasici eficienți există și în anumite cazuri speciale. De exemplu, în grupul numerelor întregi modulo p în raport cu adunarea, puterea $b k$ devine un produs $bk$ , iar egalitatea înseamnă congruență modulo p în numerele întregi. Algoritmul lui Euclid extins^⁠(d) găsește rapid p.

Cu Diffie–Hellman se folosește un grup ciclic modulo un număr prim $p$ , ceea ce permite un calcul eficient al logaritmului discret cu Pohlig–Hellman dacă ordinul grupului (fiind $p -1$ ) este suficient de neted^⁠(d), adică nu are factori primi mari.

Comparație cu factorizarea întregilor

Calculul logaritmilor discreți și factorizarea numerelor întregi sunt probleme distincte, dar cele două au unele proprietăți în comun:

ambele sunt cazuri speciale ale problemei subgrupurilor ascunse^⁠(d) pentru grupuri abeliene finite,
ambele probleme par a fi dificile (nu sunt cunoscuți algoritmi eficienți pentru calculatoarele necuantice),
pentru ambele probleme sunt cunoscuți algoritmi eficienți pe calculatoarele cuantice,
algoritmii dintr-o problemă sunt adesea adaptați la cealaltă și
dificultatea ambelor probleme a fost folosită pentru a construi diverse sisteme criptografice.

Criptografie

Există grupuri pentru care calculul logaritmilor discreți pare a fi deosebit de dificil. În unele cazuri (de exemplu, subgrupuri de ordin număr prim mare ale grupurilor (Z_p)^× ) nu numai că nu există un algoritm eficient cunoscut pentru cel mai rău caz, dar se poate demonstra că complexitatea cazului mediu este aproximativ la fel de dificilă ca și cel mai rău caz folosind autoreductibilitatea aleatorie^⁠(d).

În același timp, problema inversă a exponențierii discrete nu este dificilă (poate fi calculată eficient folosind exponențiarea prin ridicarea la pătrat^⁠(d), de exemplu). Această asimetrie este analogă cu cea dintre factorizarea numerelor întregi și înmulțirea lor. Ambele asimetrii (și alte posibile funcții unidirecționale^⁠(d)) au fost exploatate în construcția sistemelor criptografice.

Opțiunile populare pentru grupul G în criptografia cu logaritmi discreți (DLC) sunt grupurile ciclice (Z_p)^× (de ex. Criptarea ElGamal^⁠(d), schimbul de chei Diffie–Hellman^⁠(d) și Digital Signature Algorithm) și subgrupurile ciclice ale curbelor eliptice pe corpuri finite.

Deși nu există un algoritm public cunoscut pentru rezolvarea problemei logaritmului discret în general, primii trei pași ai algoritmului ciurului algebric depind doar de grupul G, nu de elementele specifice ale lui G al căror logaritm finit este dorit. Prin precalcularea^⁠(d) acestor trei pași pentru un grup specific, trebuie doar să se efectueze ultimul pas, care este mult mai puțin costisitor din punct de vedere computațional decât primii trei, pentru a obține un logaritm specific în acel grup.^[2]

Se dovedește că mare parte din traficul de Internet utilizează unul dintre puținele grupuri care sunt de ordinul a 1024 de biți sau mai puțin, de exemplu grupuri ciclice de ordinul numere prime Oakley specificate în RFC 2409 . Atacul Logjam^⁠(d) a folosit această vulnerabilitate pentru a compromite o varietate de servicii de internet care au permis utilizarea unor grupuri al căror ordin era un număr prim de 512 biți, așa-numitul export grade^⁠(d).^[2]

Autorii atacului Logjam estimează că precalcularea mult mai dificilă necesară pentru a rezolva problema logaritmului discret pentru un număr prim de 1024 de biți s-ar încadra în bugetul unei mari agenții naționale de informații,^⁠(d) cum ar fi National Security Agency (NSA) din SUA. Autorii Logjam speculează că această precalculare împotriva unor numere prime 1024 DH reutilizate pe scară largă s-ar afla în spatele afirmațiilor din documentele NSA scurse cum că NSA ar fi capabilă să spargă o mare parte din criptografia actuală.^[2]

Note

^ Shor, Peter (1997). „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing. 26 (5): 1484–1509. doi:10.1137/s0097539795293172.
^ ^a ^b ^c Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel (octombrie 2015). „Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice” (PDF).

Bibliografie

Rosen, Kenneth H. (2011). Elementary Number Theory and Its Application (ed. 6th). Pearson. p. 368. ISBN 978-0321500311.
Weisstein, Eric W. „Discrete Logarithm”. MathWorld. Wolfram Web. Accesat în 1 ianuarie 2019.

Lectură suplimentară

Richard Crandall^⁠(d) ; Carl Pomerance^⁠(d). Chapter 5, Prime Numbers: A computational perspective, ed. a 2-a, Springer.
Stinson, Douglas Robert (2006), Cryptography: Theory and Practice (ed. 3rd), London: CRC Press, ISBN 978-1-58488-508-5 978-1-58488-508-5

Portal Matematică

[1] Shor, Peter (1997). „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing. 26 (5): 1484–1509. doi:10.1137/s0097539795293172.

[imperfectfs-2] Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel (octombrie 2015). „Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice” (PDF).

[1]

[2]